#include "myGraph.h"
#include <iostream>
#include <sstream>
#include <string>
#include <queue>

using namespace std;

EdgeNode::EdgeNode(){
    dest = -1;
    link = NULL;
}

EdgeNode::EdgeNode(int dest, EdgeNode* link){
    this->dest = dest;
    this->link = link;
}

EdgeNode::~EdgeNode(){
    delete link;
}

int EdgeNode::getDest(){
    return dest;
}

EdgeNode* EdgeNode::getNext(){
    return link;
}

void EdgeNode::setDest(int dest){
    this->dest = dest;
}

void EdgeNode::setNext(EdgeNode* link){
    this->link = link;
}

VertexNode::VertexNode(){
    data = 0;
    firstEdge = NULL;
}

VertexNode::VertexNode(char data, EdgeNode* firstEdge){
    this->data = data;
    this->firstEdge = firstEdge;
}

VertexNode::~VertexNode(){
    delete firstEdge;
}

char VertexNode::getData(){
    return data;
}

EdgeNode* VertexNode::getFirstEdge(){
    return firstEdge;
}

void VertexNode::setData(char data){
    this->data = data;
}

void VertexNode::setFirstEdge(EdgeNode* firstEdge){
    this->firstEdge = firstEdge;
}

MyGraph::MyGraph(){
    nodeNum = 0;
    edgeNum = 0;
    VexList = NULL;
}

MyGraph::MyGraph(int nodeNum, int edgeNum, char* nodeList, int* edgeStartList, int* edgeEndList){
    this->nodeNum = nodeNum;
    this->edgeNum = edgeNum;
    VexList = new VertexNode[nodeNum];
    for(int i = 0; i < nodeNum; i++){
        VexList[i].setData(nodeList[i]) ;
        VexList[i].setFirstEdge(NULL);
    }

    for(int i = 0; i < edgeNum;i++){
    EdgeNode * p = new EdgeNode;
    p->setDest(edgeEndList[i]);
    p->setNext(VexList[edgeStartList[i]].getFirstEdge());
    VexList[edgeStartList[i]].setFirstEdge(p);

    p = new EdgeNode;
    p->setDest(edgeStartList[i]);
    p->setNext(VexList[edgeEndList[i]].getFirstEdge());
    VexList[edgeEndList[i]].setFirstEdge(p);
}


}

MyGraph::~MyGraph(){
    delete[] VexList;
}

int MyGraph::getNodeNum(){
    return nodeNum;
}

int MyGraph::getEdgeNum(){
    return edgeNum;
}

string MyGraph::printGraph(){
    stringstream ss;
    for(int i = 0; i < getNodeNum(); i++){
        ss << VexList[i].getData() << ": ";
        EdgeNode* p = VexList[i].getFirstEdge();
        while(p){
            ss << VexList[p->getDest()].getData();
            p = p->getNext();
            if(p != NULL) ss << " ";
        }
        if(i!=getNodeNum()-1) ss << endl;
    }
    return ss.str();
}

int MyGraph::getFirstNeighbor(int v, int* visited){

}

int MyGraph::getNextNeighbor(int v, int w, int* visited){

}
//DFS递归遍历
void MyGraph::DFS(int v, int* visited, string& result){
    visited[v] = 1;
    result += VexList[v].getData();
    result += " ";
    EdgeNode* p = VexList[v].getFirstEdge();
    while(p){
        if(visited[p->getDest()]==0) 
        DFS(p->getDest(), visited, result);
        p = p->getNext();
    }
}

string MyGraph::graph_DFS_Traverse(){
    int* visited = new int[nodeNum];
    for(int i = 0; i < nodeNum; i++) visited[i] = 0;
    string result="";
    for(int i = 0; i < nodeNum; i++){
        if(visited[i] == 0) DFS(i, visited, result);
    }
    delete[] visited;
    return result;
}

//BFS队列遍历
void MyGraph::BFS(int v, int* visited, string& result){
    queue<int> q;
    q.push(v);
    visited[v] = 1;
    result += VexList[v].getData();
    result += " ";
    while(!q.empty()){
        int u = q.front();
        q.pop();
        EdgeNode* p = VexList[u].getFirstEdge();
        while(p){
            if(visited[p->getDest()]==0){
                q.push(p->getDest());
                visited[p->getDest()] = 1;
                result += VexList[p->getDest()].getData();
                result += " ";
            }
            p = p->getNext();
        }
    }
}

string MyGraph::graph_BFS_Traverse(){
    int* visited = new int[nodeNum];
    for(int i = 0; i < nodeNum; i++) visited[i] = 0;
    string result="";
    for(int i = 0; i < nodeNum; i++){
        if(visited[i] == 0) BFS(i, visited, result);
    }
    delete[] visited;
    return result;
}
